package cn.dapeng.sort;

import cn.dapeng.utils.BuilderArray;

/**
 * @BelongProject study
 * @BelongPackage cn.dapeng.sort
 * @Description 快排算法
 * @ClassName QuickSort
 * @Author xupenghong
 * @Date 2024/8/26 9:45
 * @Version 1.0.0
 */
public class QuickSort {

    public static void sort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        sort_2(array, 0, array.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {
        // low,high 为每次处理数组时的首、尾元素索引

        //当low==high是表示该序列只有一个元素，不必排序了
        if (low >= high) {
            return;
        }
        // 选出哨兵元素和基准元素。这里左边的哨兵元素也是基准元素
        int i = low, j = high, base = arr[low];
        while (i < j) {
            //右边哨兵从后向前找
            while (arr[j] >= base && i < j) {
                j--;
            }
            //左边哨兵从前向后找
            while (arr[i] <= base && i < j) {
                i++;
            }
            if (j > i && arr[i] > arr[j]) {
                BuilderArray.swap(arr, i, j);  //交换元素
            }
        }
        if (j > low && arr[low] > arr[j]) {
            BuilderArray.swap(arr, low, j); //基准元素与右哨兵交换
        }
        //递归调用，排序左子集合和右子集合
        sort(arr, low, j - 1);
        sort(arr, j + 1, high);
    }

    public static void sort_1(int[] array, int start, int end) {

        if (start > end) {
            return;
        }

        int left = start, right = end, target = array[left];

        while (left < right) {
            while (target < array[right] && left < right) {
                right--;
            }
            while (target > array[left] && left < right) {
                left++;
            }

            if (array[left] == array[right]) {
                right--;
            } else {
                BuilderArray.swap(array, left, right);
            }
        }

        sort_1(array, start, left - 1);
        sort_1(array, left + 1, end);
    }

    /**
     * 优化版：取中间值作为基准值， 这样对于一个基本上是有序得数组，减少递归层数
     * @param array
     * @param start
     * @param end
     */
    public static void sort_2(int[] array, int start, int end) {

        if (start > end) {
            return;
        }

        int left = start, right = end, target = array[(left + right) / 2];

        while (left < right) {
            while (target < array[right] && left < right) {
                right--;
            }
            while (target > array[left] && left < right) {
                left++;
            }

            if (array[left] == array[right]) {
                right--;
            } else {
                BuilderArray.swap(array, left, right);
            }
        }

        sort_2(array, start, left - 1);
        sort_2(array, left + 1, end);
    }

    public static void main(String[] args) {
        int[] array = {5, 1, 5, 6, 5, 2, 4};
        sort(array);
        BuilderArray.print(array);
    }

}
